package lanqiaobei2020;

public class _03分配口罩 {
    /**
     * 某市市长获得了若干批口罩，每一批口罩的数目如下：
     * 9090400
     * 8499400
     * 5926800
     * 8547000
     * 4958200
     * 4422600
     * 5751200
     * 4175600
     * 6309600
     * 5865200
     * 6604400
     * 4635000
     * 10663400
     * 8087200
     * 4554000
     * 现在市长要把口罩分配给市内的 2 所医院。由于物流限制，每一批口罩只
     * 能全部分配给其中一家医院。市长希望 2 所医院获得的口罩总数之差越小越好。
     * 请你计算这个差最小是多少?
     */
    public static long res = Long.MAX_VALUE;
    public static long[] arr = {
            9090400, 8499400, 5926800, 8547000, 4958200,
            4422600, 5751200, 4175600, 6309600, 5865200,
            6604400, 4635000, 10663400, 8087200, 4554000
    };
    public static void main(String[] args) {
        dfs(0,0,0);
        System.out.println(res);
    }

    private static void dfs(int k, long sum1, long sum2) {
        if (k == arr.length){
            long abs = Math.abs(sum1 - sum2);
            res = res < abs ? res : abs;
            return;
        }
        dfs(k+1,sum1+arr[k],sum2);
        dfs(k+1,sum1,sum2+arr[k]);
    }
}
